/*
 * BiTree.c
 *
 *  Created on: 2011-12-5
 *      Author: tracl01
 */

#include "predefine.h"
//#include "SqStack.c"
//typedef int Elemtype;
typedef struct BiTNode{
	Elemtype data;
	struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;

int createBiTree(BiTree *T){		//这个结点元素输入很有意思，不能每输入一个元素回车一次
	Elemtype ch;					//而要输入完所有组成二叉树的元素再回车
	scanf("%c",&ch);
	if (ch == ' ') {				//这里根据数据类型自定义一字符或整数
		*T = NULL;
	} else {
		*T = (BiTree)malloc(sizeof(BiTNode));
		if (!*T) {
			exit(EXIT_FAILURE);
		}
		(*T)->data = ch;
		createBiTree(&((*T)->lchild));	//需要这样书写,*T要加上括号
		createBiTree(&((*T)->rchild));
	}
	return EXIT_SUCCESS;
}

void visit(Elemtype e){
	printf("%c ",e);
}

int preorderTraverse(BiTree T){			//思考递归算法就要像用数学归纳法一样，假设了f(n-1)，就要相信
	if (T) {							//f(n-1)已知，可以用它推出f（n）
		visit(T->data);
		preorderTraverse(T->lchild);
		preorderTraverse(T->rchild);
	}
	return EXIT_SUCCESS;
}

int inorderTraverse(BiTree T){
	if (T) {
		inorderTraverse(T->lchild);
		visit(T->data);
		inorderTraverse(T->rchild);
	}
	return EXIT_SUCCESS;
}
/*
int inorderTraverse_N(BiTree T){
	SqStack S; BiTree p;
	initStack(&S); push(&S, T);
	while(stackEmpty(S)){
		while(!getTop(S, &p) && p){
			push(&S, p->lchild);
		}
		pop(&S, &p);
		if (!getTop(S, &p) && p) {
			visit(p->data);
			push(&S, p->rchild);
		}
	}
	return EXIT_SUCCESS;
}
*/
int postorderTraverse(BiTree T){
	if (T) {
		postorderTraverse(T->lchild);
		postorderTraverse(T->rchild);
		visit(T->data);
	}
	return EXIT_SUCCESS;
}
/*
int main(void){
	BiTree T;
	createBiTree(&T);
	printf("create over!");
	printf("\n 先序：");
	preorderTraverse(T);
	printf("\n 中序：");
//	inorderTraverse_N(T);
	printf("\n 后序：");
	postorderTraverse(T);
	return EXIT_SUCCESS;
}
*/
